Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
The successor of a node p is the node with the smallest key greater than p.val.
Example 1:
Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105- All Nodes will have unique values.
Average Rating: 4.44 (27 votes)
Solution
Overview
This is a very popular programming interview problem and there are a couple of ways we can approach it. This problem is very similar to finding the Inorder Successor in a Binary Tree. The first solution that we will look at applies to any kind of binary tree because it does not rely on any special properties of the tree. Our second solution will take into account the sorted nature of the binary search tree and will thus, improve upon the overall time complexity of the previous solution. The inorder successor of a particular node is simply the node that comes after this node during the inorder traversal of the tree. There are a few scenarios that we must consider for the inorder successor of a node to understand our first algorithm properly.
Figure 1. Few examples of inorder successors.
Figure 2. Another unique example of an inorder successor.
Approach 1: Without using BST properties
Intuition
As mentioned in the overview section of this article, we will first discuss the approach that applies to any binary tree and is not specifically for a binary search tree. This is not the most efficient approach out there considering it doesn't incorporate the search properties associated with the structure of a binary search tree. However, for the sake of completeness, we are including this approach in the official solution since the interviewer may ask you to find the inorder successor for a binary tree :)
We hinted briefly at the different cases for the inorder successor and we will look at these cases more concretely in this solution. The algorithm is based on handling these cases one by one. There are just two cases that we need to account for in this approach.
When the node has a right child
The inorder successor in this case is the leftmost node in the tree rooted at the right child. Let's look at a couple of examples to depict this point.
Figure 3. Case 1 when the given node has a right child.
Let's look at yet another example where there is a right child who doesn't have a left child. In this case, the right child itself will be the inorder successor of the designated node.
Figure 4. Another example of when the node has a right child.
When the node doesn't have a right child
This is trickier to handle than the first case. In this case, one of the ancestors acts as the inorder successor. That ancestor can be the immediate parent, or, it can be one of the ancestors further up the tree.
Figure 5. When the node does not have the right child.
In this case, we need to perform the inorder traversal on the tree and keep track of a previous node which is the predecessor to the current node we are processing. If at any point the predecessor previous is equal to the node given to us then the current node will be its inorder successor. Why? Because we are performing the inorder traversal on the tree to find the successor node via simulation.
Algorithm
-
We define two class variables for this algorithm:
previousandinorderSuccessorNode. Thepreviousvariable will only be used when handling the second case as previously explained and theinorderSuccessorNodewill ultimately contain the result to be returned. -
Inside the function
inorderSuccessor, we first check which of the two cases we need to handle. For that, we simply check for the presence of a right child.-
The right child exists
In this case, we assign the right child to a node called
leftmostand we iterate until we reach a node (leftmost) which doesn't have a left child. We iteratively assignleftmost = leftmost.leftand that's how we will get the leftmost node in the subtree. -
The right child does not exist
- As mentioned before, this case is trickier to handle. For this, we define another function called
inorderCase2and we will pass it anodeand the nodep. - We perform simple inorder traversal and hence, we first recurse on the left child of the
node. - Then, when the recursion returns, we check if the class variable
previousis equal to the nodep. If that is the case, then it meanspis the inorder predecessor ofnodeor in other words, thenodeis the inorder successor of the nodepand we return from that point onwards. We assigninorderSuccessorNodetonodeand return from this function.
- As mentioned before, this case is trickier to handle. For this, we define another function called
-
-
Finally, we return the
inorderSuccessorNodeas our result.
Implementation
Complexity Analysis
-
Time Complexity: O(N) where N is the number of nodes in the tree.
-
For case 1, we might have a scenario where the root node has a right subtree that is left-skewed. Something like the following.
Figure 6. A skewed tree for worst-case time complexity.
In this case, we have to process all of the nodes to find the leftmost node and hence, the overall time complexity is O(N).
-
For case 2, we might have to process the entire tree before finding the inorder successor. Let's look at an example tree to understand when that might happen.
Figure 7. A skewed tree for worst-case time complexity.
-
-
Space Complexity: Space Complexity: O(N) for the second case since we might have a skewed tree leading to a recursion stack containing all N nodes. For the first case, we don't have any additional space complexity since we simply use a while loop to find the successor.
Approach 2: Using BST properties
Intuition
In the previous approach, we did not use any of the binary-search tree properties. However, the optimal solution for this problem comes from utilizing those properties and that's what we will explore in this solution. Specifically, we'll make use of the standard BST property where the left descendants have smaller values than the current node and right descendants have larger values than the current node. We don't need to handle any specific cases here and we can start with the root node directly and reach our inorder successor. Let's see the choices we have when comparing the value of the given node p to the current node in the tree.
Figure 8. Skipping half of the binary search tree.
By comparing the values of the node p and the current node in the tree during our traversal, we can discard half of the remaining nodes at each step, and thus, for a balanced binary search tree we can search for our inorder successor in logarithmic time rather than linear time. That's a huge improvement over the previous solution.
Algorithm
-
We start our traversal with the root node and continue the traversal until our current
nodereaches anullvalue i.e. there are no more nodes left to process. -
At each step we compare the value of node
pwith that ofnode.-
If
p.val >= node.valthat implies we can safely discard the left subtree since all the nodes there including the currentnodehave values less thanp.Figure 9. Skipping the left subtree.
-
However, if
p.val < node.val, that implies that the successor must lie in the left subtree and that the currentnodeis a potential candidate for inorder successor. Thus, we update our local variable for keeping track of the successor,successor, tonode.Figure 10. Skipping the right subtree and recording a potential candidate for the successor.
-
-
Return
successor.Figure 11. Returning the candidate.
We don't handle duplicate node values in the algorithm below. That is left as an exercise for the reader to solve :) It's a slight variation but an important one to understand for follow-up questions in an interview.
Implementation
Complexity Analysis
-
Time Complexity: O(N) since we might end up encountering a skewed tree and in that case, we will just be discarding one node at a time. For a balanced binary-search tree, however, the time complexity will be O(logN) which is what we usually find in practice.
-
Space Complexity: O(1) since we don't use recursion or any other data structures for getting our successor.
Combine the two solutions to allow earlier stopping:
- If p has a right leaf, we only need to traverse from p to leaf (one step right, all step left)
- Else, we only need to traverse from root to p
def inorderSuccessor_02(root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
if p.right:
curr = p.right
while curr.left:
curr = curr.left
return curr
else:
successor, curr = None, root
while curr != p:
if curr.val < p.val:
curr = curr.right
else:
successor, curr = curr, curr.left
return successor
Can someone help me understand how to tweak solution 2 to handle duplicates?
Does it depend on how we treat duplicate values? i.e. whether we choose to insert a node with equal value to its parent on the left or right?
It seems to me solution 1 is a more general solution although it uses more space due to recursion.
(Not using BST property) just take the next of p during the inorder traversal:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
curr=root
stack=[]
turn=False
while curr or stack:
while curr:
stack.append(curr)
curr=curr.left
# curr=None
# stack top is the left most
node=stack.pop()
if node.right:
curr=node.right
if turn:
return node
if node==p:
turn=True
I got both, the iterative and the recursive approaches and felt like my recursive approach was simpler than what they have put here. My iterative one was quite similar to their but still simpler imo.
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null){
return null;
}
TreeNode successor = inorderSuccessor(root.left, p);
if(successor != null){
return successor;
}
if(root.val > p.val){
return root;
}
return inorderSuccessor(root.right, p);
}
}
Last Edit: March 16, 2021 3:12 PM
Simple and concise Recursive solution using BST property( C++)
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode *candidate = NULL;
TreeNode *cur = root;
while(cur != NULL){
if(cur->val > p->val){
candidate = cur;
cur = cur->left;
}
else{
cur = cur->right;
}
}
return candidate;
}
};
In approach 1, handling cases was not really required. Second case (with some minor changes) would have need enough.
```def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
def _helper(root, p, curr_val):
if not root:
return curr_val
else:
if root.val > p.val:
return _helper(root.left, p, root)
else:
return _helper(root.right, p, curr_val)
return _helper(root, p, None)
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { }};









